import java.util.Arrays;

public class quicksort2 {//三分法处理快排
    public static void quicksort2(int[] arr,int a,int b){
        if(a<b){
            int[] brr=seachersort1(arr,a,b);
            quicksort2(arr,brr[1]+1,b);
            quicksort2(arr,a,brr[0]-1);
        }
    }
    public static int[] seachersort1(int[] arr,int a,int b){
        int begin=a+1;//扫描指针
        int end=b;//大于区指针
        int point=a+1;//等于区指针
        int pivot=arr[a];//主元值
        while(begin<=end) {
            if (begin <= end && pivot > arr[begin]) {
                int t = arr[begin];
                arr[begin] = arr[point];
                arr[point] = t;
                begin++;
                point++;
            } else if (begin <= end && pivot == arr[begin]) {
                begin++;
            } else if (begin <= end && pivot < arr[begin]) {
                int t1 = arr[begin];
                arr[begin] = arr[end];
                arr[end] = t1;
                end--;
            }
        }
        point--;
        int t2=arr[point];
        arr[point]=arr[a];
       arr[a]=t2;
      int[] arr1={point,end};
        return arr1;
    }
    public static void main(String args[]){
        int[] arr={5,12,45,5,76,33,99,21,5,5,41,1,3};
        quicksort2(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
